#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end());
        int ret = 1;
        int left = points[0][0];
        int right = points[0][1];
        for (int i = 1; i < points.size(); i++)
        {

            if (points[i][0] <= right)
            {
                left = max(left, points[i][0]);
                right = min(right, points[i][1]);
            }
            else
            {
                left = points[i][0];
                right = points[i][1];
                ret++;
            }
        }

        return ret;
    }
};

class Solution {
public:
    int integerReplacement(long long n) {
        //long long n = n;
        int step = 0;
        while (n != 1)
        {
            if (n % 2 == 0)
            {
                n /= 2;
            }
            else if (((long long)n + 1) % 4 == 0 && n > 3)
            {
                n++;
            }
            else
            {
                n--;
            }
            cout << n << " ";
            step++;
        }
        return step;
    }
};

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end());
        int m = envelopes.size();
        vector<int> dp(envelopes.size(), 1);
        dp[0] = 1;
        //int _max1 = 1;
        //vector<int> _max2 = envelopes[0];
        for (int i = 1; i < envelopes.size(); i++)
        {
            int w = envelopes[i][0];
            int h = envelopes[i][1];
            for (int j = 0; j < i; j++)
            {
                if (w > envelopes[j][0] && h > envelopes[j][1])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            //cout<<i<<":"<<dp[i]<<endl;
        }
        int _max = 0;
        for (auto e : dp)
        {
            //cout<<e<<endl;
            _max = max(_max, e);

        }
        return _max;
    }
};

class Solution {
public:
    struct Com
    {
        bool operator()(const vector<int>& l, const vector<int>& r)
        {
            return l[0] > r[0];
        }
    };
    int pileBox(vector<vector<int>>& box) {
        Com com;
        sort(box.begin(), box.end(), com);
        int m = box.size();
        vector<int> dp(m, 0);
        for (int i = 0; i < m; i++)
        {
            dp[i] = box[i][2];
        }
        int ret = 1;
        for (int i = 1; i < m; i++)
        {
            int w = box[i][0];
            int d = box[i][1];
            int h = box[i][2];
            for (int j = 0; j < i; j++)
            {
                if (w < box[j][0] && d < box[j][1] && h < box[j][2])
                {
                    dp[i] = max(dp[j] + box[i][2], dp[i]);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

class Solution {
public:
    struct Com
    {
        bool operator()(const vector<int>& l, const vector<int>& r)
        {
            return l[0] == r[0] ? l[1] > r[1]:l[0] < r[0];
        }
    };
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        Com com;
        sort(envelopes.begin(), envelopes.end(), com);
        vector<int> tmp;
        tmp.push_back(envelopes[0][1]);
        //int prev = envelopes[0][0];
        for (int i = 1; i < envelopes.size(); i++)
        {

            if (envelopes[i][1] > tmp.back())
            {
                tmp.push_back(envelopes[i][1]);
                //prev = envelopes[i][0];
            }
            else
            {
                int left = 0;
                int right = tmp.size() - 1;
                int mid = (left + right) / 2;
                int a = envelopes[i][1];
                while (left < right)
                {
                    if (tmp[mid] >= a)
                    {
                        right = mid;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                    mid = (left + right) / 2;
                }
                tmp[right] = a;
            }
        }
        for (auto e : tmp)
            cout << e << endl;


        return tmp.size();
    }
};

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int x1, x2, y1, y2;
        x1 = x2 = y1 = y2 = INT_MAX;
        int ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] % 3 == 1)
            {
                if (nums[i] <= x1)
                {
                    x2 = x1;
                    x1 = nums[i];
                }
                else if (nums[i] < x2)
                {
                    x2 = nums[i];
                }
            }
            else if (nums[i] % 3 == 2)
            {
                if (nums[i] < y1)
                {
                    y2 = y1;
                    y1 = nums[i];
                }
                else if (nums[i] < y2)
                {
                    y2 = nums[i];
                }
            }
            ret += nums[i];
        }
        if (ret % 3 == 1)
        {
            if (y1 == INT_MAX || y2 == INT_MAX)
                ret = ret - x1;
            else
                ret = max(ret - x1, ret - y1 - y2);
        }
        else if (ret % 3 == 2)
        {
            if (x1 == INT_MAX || x2 == INT_MAX)
                ret = ret - y1;
            else
                ret = max(ret - x1 - x2, ret - y1);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        sort(barcodes.begin(), barcodes.end());
        unordered_map<int, int> hash;
        int m = barcodes.size();
        for (auto e : barcodes)
        {
            hash[e]++;
        }
        int num = 0;
        int count = 0;
        for (auto& e : hash)
        {
            if (e.second > count)
            {
                count = e.second;
                num = e.first;
            }
        }
        vector<int> ret(m, 0);
        int j = 0;
        for (int i = 0; i < m; i += 2)
        {
            if (count)
            {
                ret[i] = num;
                count--;
            }
            else
            {
                while (barcodes[j] == num)
                    j++;

                ret[i] = barcodes[j++];
            }
        }
        for (int i = 1; i < m; i += 2)
        {
            while (barcodes[j] == num)
                j++;

            ret[i] = barcodes[j++];
        }
        return ret;
    }
};

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> hash;
        int size = s.size();
        for (auto e : s)
            hash[e]++;
        char maxChar;
        int maxCount = 0;
        for (auto& e : hash)
        {
            if (e.second > maxCount)
            {
                maxCount = e.second;
                maxChar = e.first;
            }
        }
        if (maxCount > (size + 1) / 2)
            return "";
        string ret(size, '\0');
        int index = 0;
        for (int i = 0; i < maxCount; i++)
        {
            ret[index] = maxChar;
            index += 2;
        }
        hash.erase(maxChar);
        for (auto [x, y] : hash)
        {
            for (int i = 0; i < y; i++)
            {
                if (index >= size)
                {
                    index = 1;
                }
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
};